package com.cty._02_HighQualityCode._19_RegularExpressions;

/**
 * @Auther: cty
 * @Date: 2020/7/6 8:38
 * @Description: 面试题19：正则表达式匹配
 * 题目：请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'
 * 表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题
 * 中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"
 * 和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。
 * @version: 1.0
 */
public class RegularExpressions {

    public static boolean match(String str, String pattern){
        if(str==null || pattern==null)
            return false;

        return matchCore(str, 0, pattern, 0);
    }  // end match()

    private static boolean matchCore(String str, int indexStr, String pattern, int indexPattern){
        String subStr = str.substring(indexStr);
        String subPattern = pattern.substring(indexPattern);

        if(subStr.equals("") && subPattern.equals(""))
            return true;

        if(subStr.equals("") || subPattern.equals(""))
            return false;

        if(subPattern.length()>=2 && subPattern.charAt(1) == '*'){
            if(subStr.charAt(0)==subPattern.charAt(0) || (!subStr.equals("") && subPattern.charAt(0)=='.')){
                return matchCore(subStr, 1, subPattern, 0) ||  // 如 "aa"&&"a*" || "aa"&&".*"
                        matchCore(subStr, 1, subPattern, 2) ||  // 如 "ab"&&"a*" || "ab"&&".*b"
                        matchCore(subStr, 0, subPattern, 2);  // 如 "b"&&".*b"
            }else
                return matchCore(subStr, 0, subPattern, 2);  // 如 "ab"&&"c*" || "c"&&"a*c"
        }

        if(subStr.charAt(0)==subPattern.charAt(0) || (!subStr.equals("") && subPattern.charAt(0)=='.'))
            return matchCore(subStr, 1, subPattern, 1);  // 如 "a"&&"a" || "a"&&".")
        return false;
    }  // end matchCore()

}  // end class
